package day1_array;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @Author: yuisama
 * @Date: 2021/8/6 18:24
 * @Description:三数之和
 * 给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？
 * 请你找出所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 示例 2：
 *
 * 输入：nums = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：nums = [0]
 * 输出：[]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Num15_threeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        // 数组元素不足3个，一定不存在三数之和，返回空集
        if (nums.length < 3) {
            return resultList;
        }
        // 将原数组排序
        Arrays.sort(nums);
        // 将排序后的数组从左开始遍历，默认nums[i] = x,则问题转换为两数之和问题
        for (int i = 0; i < nums.length; i++) {
            // 排序后的数组最小值都大于0，则一定不存在三数之和等于0的情况，返回空集
            if (nums[i] > 0) {
                return resultList;
            }
            // 去除重复元素
            // -4,-1,-1,0,1,2
            // if (nums[i] == nums[i + 1]) continue;
            // 向前看去除重复解，不能向后判断，因为此时右边元素还未处理过，左边元素一定是处理过的
            if (i > 0 && nums[i - 1] == nums[i]) continue;
            // 左右指针定义
            int l = i + 1;
            int r = nums.length - 1;
            while (l < r) {
                // sum一共有三种情况，=0则为题解，此时需要移动左右指针去除重复解
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    // 此时三个元素即为题解
                    List<Integer> tempList = new ArrayList<>();
                    tempList.add(nums[i]);
                    tempList.add(nums[l]);
                    tempList.add(nums[r]);
                    resultList.add(tempList);
                    // 移动左右指针去除重复解
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    // 移动左右指针，继续执行下一次循环判定
                    l++;
                    r--;
                }
                // 说明此时左指针对应元素偏小，左指针右移
                else if (sum < 0) {
                    l++;
                }else {
                    r--;
                }
            }
        }
        return resultList;
    }

    public static void main(String[] args) {
        Num15_threeSum test = new Num15_threeSum();
        int[] num = new int[] {-1,0,1,2,-1,-4};
        List<List<Integer>> lists = test.threeSum(num);
        System.out.println(lists);
    }
}
